package mashibing.class6;

import util.MathUtil;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-03-28
 */
public class Class6_4_SortArrayDistanceLessK {

    public static void sortDistinctLessK(int[] arr, int k) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 优先级队列默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < Math.min(arr.length, k); i++) {
            heap.add(arr[i]);
        }
        int index = 0;
        for (int i = k; i < arr.length; i++) {
            heap.add(arr[index + k]);
            arr[index++] = heap.poll();
        }
        while (!heap.isEmpty()) {
            arr[index++] = heap.poll();
        }
    }

    public static int[] generateLessKArray(int maxValue, int maxSize, int k) {
        int[] arr = new int[(int) (Math.random() * maxSize)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        Arrays.sort(arr);
        // 用于记录有没有交换过位置
        boolean[] exchange = new boolean[arr.length];
        for (int i = 0; i < arr.length; i++) {
            int curIndex = (int) (Math.random() * (k + 1)) + i;
            curIndex = Math.min(arr.length - 1, curIndex);
            if (!exchange[i] && !exchange[curIndex]) {
                exchange[i] = true;
                exchange[curIndex] = true;
                MathUtil.swap(arr, i, curIndex);
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int testCount = 500000;
        int maxValue = 20;
        int maxSize = 20;
        int maxK = 6;
        boolean flag = true;
        System.out.println("begin");
        for (int i = 0; i < testCount; i++) {
            int k = (int) (Math.random() * maxK);
            int[] arr = generateLessKArray(maxValue, maxSize, k);
            int[] arr1 = MathUtil.copyArray(arr);
            int[] arr2 = MathUtil.copyArray(arr);
            Arrays.sort(arr1);
            sortDistinctLessK(arr2,k);
            if(!MathUtil.isEqualArray(arr1, arr2)){
                flag = false;
                System.out.println("k = " + k);
                System.out.println(Arrays.toString(arr));
            }
        }
        System.out.println(flag?"success":"failure");


        int k = (int) (Math.random() * maxK);
        int[] arr = generateLessKArray(maxValue, maxSize, k);
        int[] arr1 = MathUtil.copyArray(arr);
        System.out.println("k = " + k);
        System.out.println(Arrays.toString(arr1));
        sortDistinctLessK(arr,k);
        System.out.println(Arrays.toString(arr));
    }

}
